package Hot_100;

import org.junit.Test;

public class T53_maxSubArray {
    @Test
    public void test() {
//        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int[] nums = {5,4,-1,7,8};

        int ans = maxSubArray_1(nums);
        System.out.println(ans);

    }

//    方法1 dp（未优化）
//      子问题:      以nums[i]结尾的连续子数组的最大和
//      状态转移方程: 以nums[i]结尾的连续子数组的最大和 与 以nums[i-1]结尾的连续子数组的最大和之间只相差一个元素
//                  dp[i]=dp[i-1]+nums[i]       if(dp[i-1]>0)
//                  dp[i]=nums[i]               if(dp[i-1]<=0)
//      初始值:
//      输出:
//                  每次用ans来记录dp数组的最大值,返回最大值即最终结果（不能直接返回最后一个dp,因为它不一定是最大的）
//                  dp[i]仅表示包含nums[i]结尾的连续子数组的最大和
    public int maxSubArray_1(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i - 1] <= 0) {
                dp[i] = nums[i];
            }else {
                dp[i]=dp[i-1]+nums[i];
            }
            if (ans < dp[i]) {
                ans = dp[i];
            }
        }
        return ans;
    }



//    方法2 贪心 在遍历数组的时候，如果当前指针前面的和小于0,则丢弃元素之前的连续子数组
    public int maxSubArray_2(int[] nums) {
        int sum,ans;
//        sum = ans = nums[0];
        sum=0;
        ans = nums[0];
        for (int num : nums) {
            if (sum <= 0){
                sum=num;
            }else {
                sum+=num;   //如果sum的初值为nums[0]，而nums[0]>0,那么会导致第一次结果是sum=2*sum,多算了一次
            }
            ans = Math.max(sum, ans);
        }
        return ans;
    }


//    方法3 分治法
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        return maxSubArraySum(nums, 0, len - 1);
    }

    private int maxSubArraySum(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        return max3(maxSubArraySum(nums, left, mid),
                maxSubArraySum(nums, mid + 1, right),
                maxCrossingSum(nums, left, mid, right));
    }

    private int maxCrossingSum(int[] nums, int left, int mid, int right) {
        // 一定会包含 nums[mid] 这个元素
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;
        // 左半边包含 nums[mid] 元素，最多可以到什么地方
        // 走到最边界，看看最值是什么
        // 计算以 mid 结尾的最大的子数组的和
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }
        sum = 0;
        int rightSum = Integer.MIN_VALUE;
        // 右半边不包含 nums[mid] 元素，最多可以到什么地方
        // 计算以 mid+1 开始的最大的子数组的和
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }



    private int max3(int num1, int num2, int num3) {
        return Math.max(num1, Math.max(num2, num3));
    }

}
